“Cloud Computing” has become a very visible technology in recent years. Amazon, Google, and many others companies have established various types of clouds in order to provide users with a highly scalable computing infrastructure. These clouds, frequently implemented using very large collections of servers or “server farms,” service a variety of needs ranging from large scale data storage to execution of virtual machines. One issue faced by providers of a public cloud infrastructure, or by any operator of a large, shared computer infrastructure, is how to efficiently utilize and distribute the workloads across the available system resources. Most computer systems will have peak load times, while at other times valuable resources may to unused. Examples of such resources include, but are no limited to:                CPU (e.g., FLOPS or MWIPS1, or as indicated in VMware tools, MHz)        Volatile Memory (e.g., RAM)        Storage (e.g., hard-disk space)        Network bandwidth        Power consumption        Database utilization        
Many large systems execute workload scheduler software to better utilize the available system resources. As computer systems have continued to provide increasingly larger processing capacities, however, the number of tasks scheduled for execution have also continued to increase. A large mainframe computer or server farm, for example, may have hundreds or even thousands of tasks scheduled for execution at any given point in time. With so many tasks to contend with and a finite set of resources, scheduling tasks such that all the operational constraints are met can be daunting. When such constraints cannot all be met, the workload scheduler software must choose which task requests to attempt to satisfy, deferring or even declining those task requests which cannot be met in the requested time frame. The ability of a workload scheduler to make appropriate choices among the many possible schedules depends upon the scheduler's access to relevant information about each task's scheduling requirements, including whether and how the task may be rescheduled. When resources become overcommitted, resource scheduling problems can be overshadowed by the related but different problem of optimally choosing, from among competing tasks, those task scheduling requests that will actually be fulfilled and those that will not.
Existing workload schedulers may thus not be able to adequately distribute the load at peak times of system resource utilization (wherein there may be conflicting user priorities) and troughs in utilization (wherein capacity may exceed demand). Further, existing methods of workload scheduling optimization tend to focus on the identification of processing bottlenecks and manual task ordering without taking into account which task schedules may provide greater overall value or utility. Thus, existing workload schedulers may also not adequately address situations where resources become overcommitted.